Public transport journey planning systems have been developed which allow travelers to plan their route on public transportation systems between selected start and end destinations, taking into account a selected start time or arrival time for the journey.
The journey may involve the use of more than one transport method, for example different train lines, bus routes or ferries and may involve a transit from a particular station or stop to a different vehicle running on a different route, which may involve walking to accomplish a transit between the routes.
Published schedules of train, bus and other public transportation departure and arrival times for individual stations or stops, hereinafter collectively called stations, have been used to generate data corresponding to a transit graph. The graph includes nodes which each represent a point in space-time at which an event occurs at a particular station, for example an arrival time or a departure time. Arcs joining the nodes represent paths along which the traveler can pass so that a route can be planned in terms of feasible arcs between the nodes.
Thus, by performing a query on the transit graph data, a route can be planned to provide step by step directions to reach a particular destination, using one or more forms of public transportation. The query may be performed on the transit graph data itself or on pre-computed transfer patterns for routes between particular start and end destinations, the pre-computation being performed so as to reduce the data processing required at the time that a user makes a query. For instance, a least cost process can be utilized to query the transit graph data. However, sometimes a query can return different results having the same cost.